// 08-图7 公路村村通
// Kruskal 算法实现


#include "../base/MGraph-Kruskal.c"
#include "../base/MGraph-input.c"

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    MGraph* g = createGraph(UndirectedGraph, MaxWeight, n);
    readEdgeV1WithWeight(g, m);
    printGraph(g);

    MGraph* mst = createGraph(UndirectedGraph, MaxWeight, g->vertexNum);
    int totalWeight = Kruskal(g, mst);
    printf("%d\n", totalWeight);
    printf("mst\n");
    printGraph(mst);

    freeGraph(g);
    freeGraph(mst);
    return 0;
}

